# 求最长公共子序列
def LCS(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    # 创建备忘录，求解重叠子问题
    # 令dp[i][j] 为 x[0..i-1](也就是前i个字符) 与 y[0..j-1]
    # (也就是前j个字符)的LCS长度
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # 分支1：两个子串的末尾字符相等
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            # 分支2：末尾字符不相等
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # 返回结果
    return dp[-1][-1]

# main
# x, y = 'abcd', 'acedb'
x, y = "SUANFA", "USNA"
print('最长公共子序列长度为:', LCS(x, y))
